package com.wtgroup.demo.leetcode.org_bytedance;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/explore/featured/card/bytedance/243/array-and-sorting/1019/
 */
public class Q_最长连续序列 {

    public static void main(String[] args) {
        Q_最长连续序列 exe = new Q_最长连续序列();
        // int[] nums = {100, 4, 200, 1, 3, 2};
        int[] nums = {0,3,7,2,5,8,4,6,0,1};
        int i = exe.longestConsecutive(nums);
        System.out.println(i);
    }

    /*
    * M1: 排序+扫描 (考场用这个吧)
    * M2: LC i,i+1,... 遇到 i-1 有了, 跳过.
    * M3: 并查集 (效率貌似没有M1高)
    *
    * */

    public int longestConsecutive(int[] nums) {
        if (nums.length==0) {
            return 0;
        }

        return new UnionFind(nums).maxLen;
    }

    class UnionFind {

        Map<Integer,Integer> partitions;
        Map<Integer,Integer> counts;
        int maxLen = 1;

        public UnionFind(int[] nums) {
            partitions = new HashMap<>();
            counts = new HashMap<>();

            for (int num : nums) {
                if (partitions.containsKey(num)) {
                    // 忽略重复者
                    continue;
                }
                partitions.put(num, num);
                counts.put(num, 1);

                int v1 = num-1, v2 = num+1;
                if (partitions.containsKey(v1)) {
                    union(v1, num);
                }
                if (partitions.containsKey(v2)) {
                    union(v2, num);
                }
            }

        }

        public void union(int a, int b) {
            int aroot = find(a);
            int broot = find(b);
            if (aroot!=broot) {
                int big = aroot, small = broot;
                if(counts.get(aroot) < counts.get(broot)) {
                    big = broot; small = aroot;
                }
                partitions.put(small, big);
                counts.put(big, counts.get(big) + counts.get(small));
                maxLen = Math.max(maxLen, counts.get(big));
            }
        }

        public int find(int me) {
            int parent = partitions.get(me);
            if (parent == me) {
                return parent;
            }
            parent = find(parent);
            partitions.put(me, parent);
            return parent;
        }
    }

    // -----
    // 2ms >99.8%

    /**
     * 1. 排序.
     * 2. 扫描+跳指针.
     */
    private class Solution {
        public int longestConsecutive(int[] nums) {

            if(nums.length == 0){
                return 0;
            }
            Arrays.sort(nums);

            int max = 0;
            int count = 1;
            int index = 0;
            while(index < nums.length){
                while( index < nums.length - 1 && nums[index] == nums[index+1]){
                    index++;
                }
                index ++;
                if(index == nums.length){
                    break;
                }

                if(nums[index] - nums[index-1] == 1){
                    count++;
                }else{
                    max = Math.max(max,count);
                    count = 1;
                }
            }
            max = Math.max(max,count);
            return max;
        }
    }
}
